package com.algorithm;

import java.util.Arrays;

public class MergeMain {

    public static void main(String[] args) {

        int[] arr = {1, 34, 56, 2, 3, 2, 3, 4, 1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    static void mergeSort(int[] arr) {


        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);

    }

    private static void mergeSort(int[] arr, int low, int high, int[] workspace) {

        if (low == high) return;

        int mid = low + ((high - low) >>> 1);

        mergeSort(arr, low, mid, workspace);

        mergeSort(arr, mid + 1, high, workspace);

        //[low...mid]  [mid+1,hig]
        mergeV2(arr, low, mid, high, workspace);

    }

    private static void merge(int[] arr, int low, int mid, int high, int[] workspace) {

        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                workspace[k++] = arr[i++];
            } else {
                workspace[k++] = arr[j++];
            }
        }

        while (i <= mid) {

            workspace[k++] = arr[i++];
        }

        while (j <= high) {
            workspace[k++] = arr[j++];
        }

        for (int p = 0; p < k; p++) {
            arr[low + p] = workspace[p];
        }
    }

    static void mergeV2(int[] arr, int low, int mid, int high, int[] workspace) {

        for (int i = low; i <= high; i++) {
            workspace[i] = arr[i];
        }

        int i = low, j = mid + 1;

        for (int p = low; p <=high; p++) {

            if(i==mid+1){

                arr[p]=workspace[j++];

            }else if(j==high+1){

                arr[p]=workspace[i++];

            }else if(workspace[j]>workspace[i]){

                arr[p]=workspace[i++];

            }else {
                arr[p]=workspace[j++];
            }

        }

    }

}
